#include<stdio.h>
#include<stdlib.h>

typedef int KeyType;
typedef int OtherType;
//结构定义
typedef struct
{
	KeyType key;
	OtherType other_data;
}RecordType;

//直接插入排序
void InsSort(RecordType r[],int n)
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		r[0]=r[i];j=i-1;
		while(r[0].key<r[j].key)
		{
			r[j+1]=r[j];j=j-1;
		}
		r[j+1]=r[0];
	}
}

//希尔排序
void ShellInsert(RecordType r[],int n,int delta)
{
	int i,j;
	for(i=1+delta;i<=n;i++)
		if(r[i].key<r[i-delta].key)
		{
			r[0]=r[i];
			for(j=i-delta;j>0&&r[0].key<r[j].key;j-=delta)
				r[j+delta]=r[j];
			r[j+delta]=r[0];
		}
}//ShellInsert
void ShellSort(RecordType r[],int n,int delta[],int m)
{
	int i;
	for(i=0;i<=m-1;++i)
		ShellInsert(r,n,delta[i]);
}

//冒泡排序
void BubbleSort(RecordType r[],int n)
{
	int i,j,change;
	change=1;
	for(i=1;i<=n-1&&change;++i)
	{
		change=0;
		for(j=1;j<=n-i;++j)
		    if(r[j].key>r[j+1].key)
			{
				RecordType x=r[j];
				r[j]=r[j+1];
				r[j+1]=x;
				change=1;
			}
	}
}


//快速排序
int QKPass(RecordType r[],int low,int high)
{
	RecordType x=r[low];
	while(low<high)
	{
		while(low<high&&r[high].key>=x.key)
			high--;
		if(low<high)
		{r[low]=r[high];low++;}
		while(low<high&&r[low].key<x.key)
			low++;
		if(low<high)
		{r[high]=r[low];high--;}
	}
	r[low]=x;
	return low;
}//QKPass
void QKSort(RecordType r[],int low,int high)
{
	int pos;
	if(low<high)
	{
		pos=QKPass(r,low,high);
		QKSort(r,low,pos-1);
		QKSort(r,pos+1,high);
	}
}

//简单选择排序
void SelectSort(RecordType r[],int n)
{
	int i,j,k;
	for(i=1;i<=n-1;++i)
	{
		k=i;
		for(j=i+1;j<=n;++j)
			if(r[j].key<r[k].key)  k=j;
		if(k!=i)
		{RecordType x=r[i];r[i]=r[k];r[k]=x;}
	}
}//SelectSort

//菜单
void menu()
{
	printf("\n请选择你想要实现的排序算法\n");
	printf("1.直接插入排序\n");
	printf("2.希尔排序\n");
	printf("3.冒泡排序\n");
	printf("4.快速排序\n");
	printf("5.简单选择排序\n");
}

//输入数组元素
void input(RecordType r[],int n)
{
	int i;
	printf("请输入%d个整数作为数组元素：\n",n);
	for(i=1;i<=n;i++)
	{
		printf("元素%d:",i);
		scanf("%d",&r[i].key);
		r[i].other_data=i;
	}
	getchar();
}

//输出数组内容
void output(RecordType r[],int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		printf("%d ",r[i].key);
	}
	printf("\n");
}

//函数声明
void InsSort(RecordType r[], int n);
void BubbleSort(RecordType r[], int n);
void SelectSort(RecordType r[], int n);
void ShellSort(RecordType r[], int n, int delta[], int m);
int QKPass(RecordType r[], int low, int high);
void QKSort(RecordType r[], int low, int high);
void input(RecordType r[],int n);
void output(RecordType r[],int n);

int main()
{
	int n,choice,i;
	RecordType *r;
	int delta[3]= {5,3,1}; // 希尔排序的增量序列
	// 输入数组长度
	printf("请输入数组元素个数：");
	scanf("%d", &n);
	// 动态分配数组内存
	r=(RecordType*)malloc((n+1)*sizeof(RecordType));
	if(r==NULL)
	{
		printf("内存分配失败！");
		return 1;
	}
	// 输入数组元素
	input(r, n);
	// 显示菜单并选择排序算法
	do 
	{
		menu();
		printf("请输入你的选择(1-5，0退出)：");
		scanf("%d", &choice);	
		switch (choice) 
		{
			case 1:
				InsSort(r, n);
				printf("直接插入排序结果：");
				break;
			case 2:
				ShellSort(r, n, delta, 3);
				printf("希尔排序结果：");
				break;
			case 3:
				BubbleSort(r, n);
				printf("冒泡排序结果：");
				break;
			case 4:
				QKSort(r, 1, n);
				printf("快速排序结果：");
				break;
			case 5:
				SelectSort(r, n);
				printf("简单选择排序结果：");
				break;
			case 0:
				printf("程序已退出\n");
				break;
			default:
				printf("无效的选择，请重新输入！\n");
				continue;
		}
		// 只有选择有效排序算法时才输出结果
		if (choice>=1&&choice<=5) 
		{
			output(r,n);
		}
		}while (choice!=0);
	// 释放内存
	free(r);
	return 0;
}

